package leetcode;

import Tree.CreateByPreAndIn;
import Tree.TreeNode;

public class DiameterOfTree {

	public static void main(String[] args) {
		int[] pre = {1, 2};
		int[] in = {2, 1};
		TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
		DiameterOfTree object = new DiameterOfTree();
		System.out.println(object.diameterOfBinaryTree(root));
	}
	
	//因为可以不穿过root节点，所以最大直径有三种可能
    //1.root左子树上的最大距离
    //2.root右子树上的最大距离
    //3.root左子树高度 + root右子树高度
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)){
            return 0;
        }
        int[] record = new int[1];
        postOrder(root, record);
        return record[0];
    }
    
    //返回离根最远的距离，record[0] 记录最大直径
    public int postOrder(TreeNode root, int[] record){
        if(root == null){
            record[0] = 0;
            return 0;
        }
        int leftHeight = postOrder(root.left, record);
        int leftMaxDiameter = record[0];
        int rightHeight = postOrder(root.right, record);
        int rightMaxDiameter = record[0];
        int curMax = leftHeight + rightHeight;
        record[0] = Math.max(Math.max(leftMaxDiameter, rightMaxDiameter), curMax);
        return Math.max(leftHeight, rightHeight) + 1;
    }
}
